package binary_tree

// 二叉搜索树转换双向链表

func TreeToDoublyList(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	var dfs func(node *TreeNode) (head, tail *TreeNode)
	dfs = func(node *TreeNode) (head, tail *TreeNode) {
		if node == nil {
			return
		}
		// 递归 左子树
		lHead, lTail := dfs(node.left)
		if lHead != nil {
			// 左子树不为空，头结点为左子树的头结点，并拼接当前节点到左子树的尾节点
			head = lHead
			lTail.right = node
			node.left = lTail
		} else {
			// 左子树为空，头结点为当前节点
			head = node
		}
		// 递归，右子树
		rHead, rTail := dfs(node.right)
		if rTail != nil {
			// 右子树不为空，尾节点为右子树的尾节点，并拼接当前节点到右子树的头结点
			tail = rTail
			node.right = rHead
			rHead.left = node
		} else {
			// 右子树为空，尾节点为当前节点
			tail = node
		}
		return
	}

	head, tail := dfs(root)
	// 最后将返回的头尾节点拼接成环
	tail.right = head
	head.left = tail
	return head
}
